package com.example.demo.leetcode.codetop.bytedance;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.List;

/**
 * @author xujimou
 * @version 2.0
 * @Description
 * 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
 *
 * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,3]
 * 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
 * 示例 2：
 *
 * 输入：nums = [0]
 * 输出：[[],[0]]
 *
 *

 *    初始结果集合:[]
 *               | 1
 *            [1]     []
 *               |2
 *          [1,2]    [2]   [1]  []
 *               |3
 *         [1,2,3]  [2,3] [1,3] [3]  [1,2]    [2]   [1]  []
 *
 *  查看树状图，
 *  (1)刚开始结果集是个空集，空集去添加  1
 *  (2)第二次遍历 结果集里面有 空集,1  去添加2  得到 空集，1，2,12
 *  (3)依次递归获取到所有结果集
 *
 *  第一层遍历: 1  2  3
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/subsets
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2022/2/22 14:59
 */
public class 子集 {

    private static List<List<Integer>> resList = new ArrayList<>();

    public static List<List<Integer>> subsets(int[] nums) {

        List<Integer> list = new ArrayList<>();
        for(int num : nums){
            list.add(num);
        }
        resList.add(new ArrayList<>());
        process(list);
        return resList;
    }

    /**
     * @Desciption:
     * @param list:
     */
    public static void process(List<Integer> list){
        if(list.isEmpty()){
            return;
        }
        Integer num = list.remove(0);
        int size = resList.size();
        for(int i = 0;i<size;i++){
            List<Integer> res = new ArrayList<>(resList.get(i));
            res.add(num);
            resList.add(res);
        }
        process(list);

    }

    //如何求一个数组的所有集合？ 定义一个空集合，放到一个list<List<>>中，每次便利这个list中的所有集合，将数组中的值加入集合，然后重新塞回 list<list<>>
    public static void main(String[] args) {

        int [] arr = {0};
        System.out.println(subsets(arr));
    }

}
